home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / SplayPQ.ccP,v < prev    next >
Text File  |  1989-03-22  |  11KB  |  589 lines
  1. head     1.1;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @@;
  7.  
  8.  
  9. 1.1
  10. date     89.03.22.16.16.38;  author grunwald;  state Exp;
  11. branches ;
  12. next     ;
  13.  
  14.  
  15. desc
  16. @@
  17.  
  18.  
  19.  
  20. 1.1
  21. log
  22. @Initial revision
  23. @
  24. text
  25. @// This may look like C code, but it is really -*- C++ -*-
  26. /* 
  27. Copyright (C) 1988 Free Software Foundation
  28.     written by Doug Lea (dl@@rocky.oswego.edu)
  29.  
  30. This file is part of GNU CC.
  31.  
  32. GNU CC is distributed in the hope that it will be useful,
  33. but WITHOUT ANY WARRANTY.  No author or distributor
  34. accepts responsibility to anyone for the consequences of using it
  35. or for whether it serves any particular purpose or works at all,
  36. unless he says so in writing.  Refer to the GNU CC General Public
  37. License for full details.
  38.  
  39. Everyone is granted permission to copy, modify and redistribute
  40. GNU CC, but only under the conditions described in the
  41. GNU CC General Public License.   A copy of this license is
  42. supposed to have been given to you along with GNU CC so you
  43. can know your rights and responsibilities.  It should be in a
  44. file named COPYING.  Among other things, the copyright notice
  45. and this notice must be preserved on all copies.  
  46. */
  47.  
  48. #include <stream.h>
  49. #include <assert.h>
  50. #include "<T>SplayPQ.h"
  51.  
  52.  
  53. /* 
  54.  
  55.  struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985
  56.  splay tree algorithms
  57.  
  58.  All routines use a version of their `simple top-down' splay alg. (p 669)
  59.  
  60. */
  61.  
  62. struct _dummySplayNode
  63. {
  64.   <T>SplayNode*    lt;
  65.   <T>SplayNode*    rt;
  66.   <T>SplayNode*    par;
  67. } _dummy_null;
  68.  
  69. //
  70. //    Block heap management for splay nodes
  71. //
  72.  
  73. static const int AllocateChunk = DEFAULT_INITIAL_CAPACITY * 2;
  74. static <T>SplayNode *<T>freeList = 0;
  75.  
  76. <T>SplayNode *
  77. <T>SplayNode::operator new(long)
  78. {
  79.     if ( <T>freeList == 0 ) {
  80.     <T>SplayNode *p = (<T>SplayNode *)
  81.         new char[ sizeof(<T>SplayNode) * AllocateChunk ];
  82.     <T>SplayNode *follow = 0;
  83.     <T>SplayNode *n = p;
  84.     for (int i = 0; i < AllocateChunk; i++ ) {
  85.         n -> lt = follow;
  86.         follow = n;
  87.         n++;
  88.     }
  89.     <T>freeList = &( p[AllocateChunk - 1] );
  90.     }
  91.  
  92.     <T>SplayNode *t = <T>freeList;
  93.     <T>freeList = <T>freeList -> lt;
  94.  
  95.     return( t );
  96. }
  97.  
  98. void
  99. <T>SplayNode::operator delete(void *pp)
  100. {
  101.     <T>SplayNode *p = (<T>SplayNode *) pp;
  102.     p -> lt = <T>freeList;
  103.     <T>freeList = p;
  104. }
  105.  
  106.  
  107. /*
  108.  traversal primitives
  109. */
  110.  
  111.  
  112. <T>SplayNode* <T>SplayPQ::leftmost()
  113. {
  114.   <T>SplayNode* t = root;
  115.   if (t != 0) while (t->lt != 0) t = t->lt;
  116.   return t;
  117. }
  118.  
  119. <T>SplayNode* <T>SplayPQ::rightmost()
  120. {
  121.   <T>SplayNode* t = root;
  122.   if (t != 0) while (t->rt != 0) t = t->rt;
  123.   return t;
  124. }
  125.  
  126. <T>SplayNode* <T>SplayPQ::succ(<T>SplayNode* t)
  127. {
  128.   if (t == 0)
  129.     return 0;
  130.   if (t->rt != 0)
  131.   {
  132.     t = t->rt;
  133.     while (t->lt != 0) t = t->lt;
  134.     return t;
  135.   }
  136.   else
  137.   {
  138.     for (;;)
  139.     {
  140.       if (t->par == 0 || t == t->par->lt)
  141.         return t->par;
  142.       else
  143.         t = t->par;
  144.     }
  145.   }
  146. }
  147.  
  148. <T>SplayNode* <T>SplayPQ::pred(<T>SplayNode* t)
  149. {
  150.   if (t == 0)
  151.     return 0;
  152.   else if (t->lt != 0)
  153.   {
  154.     t = t->lt;
  155.     while (t->rt != 0) t = t->rt;
  156.     return t;
  157.   }
  158.   else
  159.   {
  160.     for (;;)
  161.     {
  162.       if (t->par == 0 || t == t->par->rt)
  163.         return t->par;
  164.       else
  165.         t = t->par;
  166.     }
  167.   }
  168. }
  169.  
  170.  
  171. Pix <T>SplayPQ::seek(<T&> key)
  172. {
  173.   <T>SplayNode* t = root;
  174.   if (t == 0)
  175.     return 0;
  176.  
  177.   int comp = <T>CMP(key, t->item);
  178.   if (comp == 0)
  179.     return Pix(t);
  180.  
  181.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  182.   <T>SplayNode* l = dummy;
  183.   <T>SplayNode* r = dummy;
  184.   dummy->rt = dummy->lt = dummy->par = 0;
  185.  
  186.   while (comp != 0)
  187.   {
  188.     if (comp > 0)
  189.     {
  190.       <T>SplayNode* tr = t->rt;
  191.       if (tr == 0)
  192.         break;
  193.       else
  194.       {
  195.         comp = <T>CMP(key, tr->item);
  196.         if (comp <= 0 || tr->rt == 0)
  197.         {
  198.           l->rt = t; t->par = l;
  199.           l = t;
  200.           t = tr;
  201.           if (comp >= 0)
  202.             break;
  203.         }
  204.         else
  205.         {
  206.           if ((t->rt = tr->lt) != 0) t->rt->par = t;
  207.           tr->lt = t; t->par = tr;
  208.           l->rt = tr; tr->par = l;
  209.           l = tr;
  210.           t = tr->rt;
  211.           comp = <T>CMP(key, t->item);
  212.         }
  213.       }
  214.     }
  215.     else
  216.     {
  217.       <T>SplayNode* tl = t->lt;
  218.       if (tl == 0)
  219.         break;
  220.       else
  221.       {
  222.         comp = <T>CMP(key, tl->item);
  223.         if (comp >= 0 || tl->lt == 0)
  224.         {
  225.           r->lt = t; t->par = r;
  226.           r = t;
  227.           t = tl;
  228.           if (comp <= 0)
  229.             break;
  230.         }
  231.         else
  232.         {
  233.           if ((t->lt = tl->rt) != 0) t->lt->par = t;
  234.           tl->rt = t; t->par = tl;
  235.           r->lt = tl; tl->par = r;
  236.           r = tl;
  237.           t = tl->lt;
  238.           comp = <T>CMP(key, t->item);
  239.         }
  240.       }
  241.     }
  242.   }
  243.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  244.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  245.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  246.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  247.   t->par = 0;
  248.   root = t;
  249.   return (comp == 0) ? Pix(t) : 0;
  250. }
  251.  
  252.  
  253. Pix <T>SplayPQ::enq(<T&> item)
  254. {
  255.   ++count;
  256.   <T>SplayNode* newnode = new <T>SplayNode(item);
  257.   <T>SplayNode* t = root;
  258.   if (t == 0)
  259.   {
  260.     root = newnode;
  261.     return Pix(root);
  262.   }
  263.  
  264.   int comp = <T>CMP(item, t->item);
  265.  
  266.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  267.   <T>SplayNode* l = dummy;
  268.   <T>SplayNode* r = dummy;
  269.   dummy->rt = dummy->lt = dummy->par = 0;
  270.   
  271.   int done = 0;
  272.   while (!done)
  273.   {
  274.     if (comp >= 0)
  275.     {
  276.       <T>SplayNode* tr = t->rt;
  277.       if (tr == 0)
  278.       {
  279.         tr = newnode;
  280.         comp = 0; done = 1;
  281.       }
  282.       else
  283.         comp = <T>CMP(item, tr->item);
  284.         
  285.       if (comp <= 0)
  286.       {
  287.         l->rt = t; t->par = l;
  288.         l = t;
  289.         t = tr;
  290.       }
  291.       else 
  292.       {
  293.         <T>SplayNode* trr = tr->rt;
  294.         if (trr == 0)
  295.         {
  296.           trr =  newnode;
  297.           comp = 0; done = 1;
  298.         }
  299.         else
  300.           comp = <T>CMP(item, trr->item);
  301.  
  302.         if ((t->rt = tr->lt) != 0) t->rt->par = t;
  303.         tr->lt = t; t->par = tr;
  304.         l->rt = tr; tr->par = l;
  305.         l = tr;
  306.         t = trr;
  307.       }
  308.     }
  309.     else
  310.     {
  311.       <T>SplayNode* tl = t->lt;
  312.       if (tl == 0)
  313.       {
  314.         tl = newnode;
  315.         comp = 0; done = 1;
  316.       }
  317.       else
  318.         comp = <T>CMP(item, tl->item);
  319.  
  320.       if (comp >= 0)
  321.       {
  322.         r->lt = t; t->par = r;
  323.         r = t;
  324.         t = tl;
  325.       }
  326.       else
  327.       {
  328.         <T>SplayNode* tll = tl->lt;
  329.         if (tll == 0)
  330.         {
  331.           tll = newnode;
  332.           comp = 0; done = 1;
  333.         }
  334.         else
  335.           comp = <T>CMP(item, tll->item);
  336.  
  337.         if ((t->lt = tl->rt) != 0) t->lt->par = t;
  338.         tl->rt = t; t->par = tl;
  339.         r->lt = tl; tl->par = r;
  340.         r = tl;
  341.         t = tll;
  342.       }
  343.     }
  344.   }
  345.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  346.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  347.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  348.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  349.   t->par = 0;
  350.   root = t;
  351.   return Pix(root);
  352. }
  353.  
  354.  
  355. void <T>SplayPQ::del(Pix pix)
  356. {
  357.   <T>SplayNode* t = (<T>SplayNode*)pix;
  358.   if (t == 0) return;
  359.  
  360.   <T>SplayNode* p = t->par;
  361.  
  362.   --count;
  363.   if (t->rt == 0)
  364.   {
  365.     if (t == root)
  366.     {
  367.       if ((root = t->lt) != 0) root->par = 0;
  368.     }
  369.     else if (t == p->lt)
  370.     {
  371.       if ((p->lt = t->lt) != 0) p->lt->par = p;
  372.     }
  373.     else
  374.       if ((p->rt = t->lt) != 0) p->rt->par = p;
  375.   }
  376.   else
  377.   {
  378.     <T>SplayNode* r = t->rt;
  379.     <T>SplayNode* l = r->lt;
  380.     for(;;)
  381.     {
  382.       if (l == 0)
  383.       {
  384.         if (t == root)
  385.         {
  386.           root = r;
  387.           r->par = 0;
  388.         }
  389.         else if (t == p->lt) 
  390.         {
  391.           p->lt = r;
  392.           r->par = p;
  393.         }
  394.         else
  395.         {
  396.           p->rt = r;
  397.           r->par = p;
  398.         }
  399.         if ((r->lt = t->lt) != 0) r->lt->par = r;
  400.         break;
  401.       }
  402.       else
  403.       {
  404.         if ((r->lt = l->rt) != 0) r->lt->par = r;
  405.         l->rt = r; r->par = l;
  406.         r = l;
  407.         l = l->lt;
  408.       }
  409.     }
  410.   }
  411.   delete t;
  412. }
  413.  
  414. <T>& <T>SplayPQ::front()
  415. {
  416.   if (root == 0)
  417.     error ("min: empty tree\n");
  418.   else
  419.   {
  420.     <T>SplayNode* t = root;
  421.     <T>SplayNode* l = root->lt;
  422.     for(;;)
  423.     {
  424.       if (l == 0)
  425.       {
  426.         root = t;
  427.         root->par = 0;
  428.         return root->item;
  429.       }
  430.       else
  431.       {
  432.         if ((t->lt = l->rt) != 0) t->lt->par = t;
  433.         l->rt = t; t->par = l;
  434.         t = l;
  435.         l = l->lt;
  436.       }
  437.     }
  438.   }
  439. }
  440.  
  441. void <T>SplayPQ::del_front()
  442. {
  443.   if (root != 0)
  444.   {
  445.     --count;
  446.     <T>SplayNode* t = root;
  447.     <T>SplayNode* l = root->lt;
  448.     if (l == 0)
  449.     {
  450.       if ((root = t->rt) != 0) root->par = 0;
  451.       delete t;
  452.     }
  453.     else
  454.     {
  455.       for(;;)
  456.       {
  457.         <T>SplayNode* ll = l->lt;
  458.         if (ll == 0)
  459.         {
  460.           if ((t->lt = l->rt) != 0) t->lt->par = t;
  461.           delete l;
  462.           break;
  463.         }
  464.         else
  465.         {
  466.           <T>SplayNode* lll = ll->lt;
  467.           if (lll == 0)
  468.           {
  469.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  470.             delete ll;
  471.             break;
  472.           }
  473.           else
  474.           {
  475.             t->lt = ll; ll->par = t;
  476.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  477.             ll->rt = l; l->par = ll;
  478.             t = ll;
  479.             l = lll;
  480.           }
  481.         }
  482.       }
  483.     }
  484.   }
  485. }
  486.  
  487. <T> <T>SplayPQ::deq()
  488. {
  489.   if (root == 0)
  490.     error("deq: empty tree");
  491.   else
  492.   {
  493.     --count;
  494.     <T>SplayNode* t = root;
  495.     <T>SplayNode* l = root->lt;
  496.     if (l == 0)
  497.     {
  498.       if ((root = t->rt) != 0) root->par = 0;
  499.       <T> res = t->item;
  500.       delete t;
  501.       return res;
  502.     }
  503.     else
  504.     {
  505.       for(;;)
  506.       {
  507.         <T>SplayNode* ll = l->lt;
  508.         if (ll == 0)
  509.         {
  510.           if ((t->lt = l->rt) != 0) t->lt->par = t;
  511.           <T> res = l->item;
  512.           delete l;
  513.           return res;
  514.         }
  515.         else
  516.         {
  517.           <T>SplayNode* lll = ll->lt;
  518.           if (lll == 0)
  519.           {
  520.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  521.             <T> res = ll->item;
  522.             delete ll;
  523.             return res;
  524.           }
  525.           else
  526.           {
  527.             t->lt = ll; ll->par = t;
  528.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  529.             ll->rt = l; l->par = ll;
  530.             t = ll;
  531.             l = lll;
  532.           }
  533.         }
  534.       }
  535.     }
  536.   }
  537. }
  538.  
  539.  
  540. void <T>SplayPQ::_kill(<T>SplayNode* t)
  541. {
  542.   if (t != 0)
  543.   {
  544.     _kill(t->lt);
  545.     _kill(t->rt);
  546.     delete t;
  547.   }
  548. }
  549.  
  550.  
  551. <T>SplayNode* <T>SplayPQ::_copy(<T>SplayNode* t)
  552. {
  553.   if (t != 0)
  554.   {
  555.     <T>SplayNode* l = _copy(t->lt);
  556.     <T>SplayNode* r = _copy(t->rt);
  557.     <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
  558.     if (l != 0) l->par = x;
  559.     if (r != 0) r->par = x;
  560.     return x;
  561.   }
  562.   else 
  563.     return 0;
  564. }
  565.  
  566. int <T>SplayPQ::OK()
  567. {
  568.   int v = 1;
  569.   if (root == 0) 
  570.     v = count == 0;
  571.   else
  572.   {
  573.     int n = 1;
  574.     <T>SplayNode* trail = leftmost();
  575.     <T>SplayNode* t = succ(trail);
  576.     while (t != 0)
  577.     {
  578.       ++n;
  579.       v &= <T>CMP(trail->item, t->item) < 0;
  580.       trail = t;
  581.       t = succ(t);
  582.     }
  583.     v &= n == count;
  584.   }
  585.   if (!v) error("invariant failure");
  586.   return v;
  587. }
  588. @
  589.